package org.zxp.algorithm.recurrence;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: effectiveJava
 * @description: 测试递归函数的调用
 * @author: X-Pacific zhang
 * @create: 2019-07-14 17:11
 **/
public class RecurrenceTest {
    public static void main(String[] args){
    }

    Map<Integer,Integer> map = new HashMap<>();

    /**
     * 假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个，请问走这 n 个台阶有多少种走法？
     */
    @Test
    public void testStairs(){
        int n = 5;
        RecurrenceTest recurrenceTest = new RecurrenceTest();
        System.out.println("一个"+n+"阶台阶共有："+recurrenceTest.getStairs(n)+"种走法");
    }

    public int getStairs(int n){
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if(map.containsKey(n)){
            return map.get(n);
        }
        int count = getStairs(n-1) + getStairs(n-2);
        map.put(n,count);
        return count;
    }

    /**
     * 假设你在一个电影院，你想知道自己坐在哪一排，但是前面人很多，你懒得去数了，于是你问前一排的人「你坐在哪一排？」，这样前面的人 (代号 A) 回答你以后，你就知道自己在哪一排了——只要把 A 的答案加一，就是自己所在的排了
     */
    @Test
    public void testRow(){
//        f(1) = 1
//        f(n) = f(n-1) + 1
        int n = 100;
        RecurrenceTest recurrenceTest = new RecurrenceTest();
        System.out.println(recurrenceTest.getRow(n));
    }

    public int getRow(int n){
        if(n == 1)return 1;
        return getRow(n-1)+1;
    }


    /**
     * 例如给出正整数 n=12345，希望以各位数的逆序形式输出，即输出54321。
     * 递归思想：首先输出这个数的个位数，然后再输出前面数字的个位数，直到之前没数字。
     */
    @Test
    public void testInvertedOrder(){
//        if(n.lengh = 1)return n;
//        f(n) = f(n-1) + 个位
        String strs = "12345";
        RecurrenceTest recurrenceTest = new RecurrenceTest();
        System.out.println(recurrenceTest.getNum(strs));
//        System.out.println(strs.substring(0, strs.length() - 1));
    }

    public String getNum(String strs){
        if(strs.length() == 1)return strs;
        return strs.substring(strs.length() - 1 ,strs.length()) + getNum(strs.substring(0, strs.length() - 1)) ;
    }


    /**
     * 一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子
     */
    @Test
    public void testDuck(){
        RecurrenceTest recurrenceTest = new RecurrenceTest();
        recurrenceTest.getDuck(1);
    }

    public int getDuck(int n){
        if(n == 8){
            System.out.println("第"+n+"个村庄的鸭子总数:"+2);
            return 2;
        }
        int value = 2*getDuck(n+1) + 2;
        System.out.println("第"+n+"个村庄的鸭子总数:"+value+" 卖掉："+(value/2+1)+" 剩余："+(value - (value/2+1)));
        return value;
    }


}
